package main.adt.list;

/**
 * Created by july on 2015/12/15.
 * 线性表的链式存储---双向链表
 * 基本操作：
 *  1、初始化一个空的链表
 *  2、以指定元素初始化链表
 *
 *  3、添加数据到链表表尾
 *  4、添加数据到链表指定位置
 *
 *  5、移除链表表尾部数据
 *  6、移除链表指定位置的数据
 *  7、清空链表
 *
 *  8、修改链表指定位置的数据
 *
 *  9、查询指定位置的数据
 *  10、查询指定数据在链表中首次出现的位置
 *
 *  11、获取链表中元素个数
 *  12、判断链表是否为空
 */
public class DoubleLinkedList<E> {

    private int size;       //元素个数
    private Node header;    //头节点
    private Node tail;      //尾节点

    public DoubleLinkedList(){
        header = tail = null;
    }

    public DoubleLinkedList(E element){
        header = tail = new Node(element,null,null);
        size++;
    }

    /**
     * 添加数据到链表表尾
     * @param element
     * @return
     */
    public boolean add(E element){
        return  addAtTail(element);
    }

    /**
     * 由于双向链表同时保留了节点的直接前驱和直接后继，所以在插入和删除操作上比单链表要稍微复杂一点
     * 那为什么还要用双向链表呢？这个问题问的好，想知道答案，想一想查询指定位置的节点元素这个方法
     * 有什么不同
     * logic:
     *      如果在表首插入数据直接调用头插法
     *      如果在表尾插入数据直接调用尾插法
     *      其他情况：先查询要插入位置的数据，然后新增一节点(前驱指向原来节点的前驱，后继指向原来的结点)
     *      修改原节点前驱的后继为新节点，原节点的前驱指向新节点
     * @param index
     * @param element
     * @return
     */
    public boolean add(int index,E element){
        checkAddIndex(index);
        if(index == 0){
            addAtHeader(element);
        }else if(index == size){
            addAtTail(element);
        }else{
            Node current = getNodeByIndex(index);
            Node newObj = new Node(element,current.prev,current);
            current.prev.next = newObj;
            current.prev = newObj;
            size++;
        }
        return true;
    }

    /**
     * 从表尾移除数据。
     * @return
     */
    public E remove(){
        return removeByIndex(size - 1);
    }

    /**
     * 移除指定位置的数据
     * logic:
     *      如果表中只有1条数据，调用清空表方法
     *      如果表中的数据多于1
     *          如果删除位置是表首，就将原头节点的后继作为头节点，并将当前头节点的前驱置空
     *          如果删除位置是表尾，就将原尾节点的前驱作为尾节点。并将当前尾节点的后继置空
     *          如果是其他位置，就将原节点的后继的前驱指向原节点的前驱，原节点的前驱的后继指向
     *         原节点的后继。
     * @param index
     * @return
     */
    public E removeByIndex(int index){
        checkIndex(index);
        Node node = getNodeByIndex(index);
        if(size == 1){
            clear();
        }else{
            if(index == 0){
                header = header.next;
                header.prev = null;
            }else if(index == size - 1){
                tail = tail.prev;
                tail.next = null;
            }else{
                node.next.prev = node.prev;
                node.prev.next = node.next;
            }
            node.prev = node.next = null;
            size--;
        }
        return node.data;
    }

    /**
     * 清空链表
     */
    public void clear(){
        header = tail = null;
        size = 0;
    }

    /**
     * 修改指定位置的数据
     * @param index
     * @param element
     * @return
     */
    public boolean set(int index,E element){
        checkIndex(index);
        Node node = getNodeByIndex(index);
        node.data = element;
        return true;
    }

    /**
     * 查询指定位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        return getNodeByIndex(index).data;
    }

    /**
     * 查询指定数据在链表中首次出现的位置，如果不存在返回-1
     */
    public int indexOf(E element){
        int count = 0;
        for(Node current = header;current != null;current = current.next){
            if(element == null){
                if(current.data == null){
                    return count;
                }
            }else{
                if(element.equals(current.data)){
                    return count;
                }
            }
            count++;
        }
        return -1;
    }


    /**
     * 判断集合是否为空
     * @return true:空；false：不为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 获取集合中元素个数
     * @return
     */
    public int size(){
        return size;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString(){
        if(size == 0){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        for(Node current = header;current != null;current = current.next){
            if(current.data != null){
                sb.append(current.data.toString()).append(",");
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    /**
     * 检查插入位置，插入位置不能小于0且不能大于集合中的元素个数
     * @param index
     */
    private void checkAddIndex(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("插入位置有误，当前集合元素个数为：" + size +" 插入位置却为：" + index +" 明显不对嘛");
        }
    }

    /**
     *检查查询位置
     * @param index
     */
    private void checkIndex(int index){
        if(index < 0 || index > size - 1){
            throw new IndexOutOfBoundsException("指定索引位置有误");
        }
    }

    /**
     * 头插法
     * 从空表开始不断添加新节点到表头，操作顺序为先创建新节点(前驱为null，后继指向原头节点)
     * 然后修改原来头节点的前驱为新节点，新的节点赋值给头节点。
     * @param element
     * @return
     */
    private boolean addAtHeader(E element){
        if(size == 0){
            header = tail = new Node(element,null,null);
        }else{
            Node newNode = new Node(element,null,header);
            header.prev = newNode;
            header = newNode;
        }
        size++;
        return true;
    }

    /**
     * 尾插法
     * 从空表开始不断添加新节点到表尾，操作顺序为先创建新节点(后继为null，前驱指向原尾节点)
     * 然后修改原来尾节点的后继为新节点，新的节点赋值给尾节点。
     * @param element
     * @return
     */
    private boolean addAtTail(E element){
        if(size == 0){
            header = tail = new Node(element,null,null);
        }else{
            Node newNode = new Node(element,tail,null);
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }

    /**
     * 查询指定位置的节点元素
     * 由于是双向链表结构，节点既保留了前驱指针也保留了后继的指针，所以在查找指定位置的节点时既可以从
     * 头节点开始往后查也可以从尾节点开始往前查，先判断索引是处于链表的前半部分还是后半部分，如果索引小于
     * 几何元素个数的一半就从前往后查，反之从后往前查。时间复杂度O(log n)
     * @param index
     * @return
     */
    private Node getNodeByIndex(int index){
        checkIndex(index);
        int count = 0;
        if(index <= size >> 1){
            for(Node current = header; current != null; current = current.next){
                if(count == index){
                    return current;
                }
                count++;
            }
        }
        for(Node current = tail; current != null; current = current.prev){
            if(count == (size - index - 1)){
                return current;
            }
            count++;
        }
        return null;
    }

    private class Node{
        private E data;         //数据域
        private Node prev;      //指针域,指向它的直接前驱
        private Node next;      //指针域,指向它的直接后继

        protected Node(E element, Node prev,Node next) {
            this.data = element;
            this.prev = prev;
            this.next = next;
        }
    }
}
